package practice;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        TreeNode root = buildTree(new LinkedList<>(Arrays.asList(3, 2, 9, null, null, 10, null, null, 8, null, 4)));
        System.out.println("-------preRootOrderTraversal-------");
        preRootOrderTraversal(root);
        System.out.println();
        stackPreOrderTraversal(root);
        System.out.println();
        System.out.println("-------midRootOrderTraversal-------");
        midRootOrderTraversal(root);
        System.out.println();
        stackMidOrderTraversal(root);
        System.out.println();
        System.out.println("-------postRootOrderTraversal-------");
        postRootOrderTraversal(root);
        System.out.println();
        stackPostOrderTraversal(root);
        System.out.println();

        System.out.println("\n\n--------layer traversal----------");
        layerTraversal(root);
    }

    /**
     * 层序遍历
     * @param root
     */
    static void layerTraversal(TreeNode<?> root) {
        if(root == null)
            return;
        Queue<TreeNode<?>> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode<?> cur;
        while((cur = queue.poll()) != null) {
            System.out.print(cur.value + " ");
            if(cur.left != null)
                queue.offer(cur.left);
            if(cur.right != null)
                queue.offer(cur.right);
        }
        System.out.println();
    }

    /**
     * 使用栈先序遍历
     * @param root
     */
    static void stackPreOrderTraversal(TreeNode<?> root) {
        if(root == null)
            return;
        Stack<TreeNode<?>> stack = new Stack<>();
        TreeNode<?> cur = root;
        boolean flag = false;
        for(;;) {
            if(flag) {
                if(cur.right != null) {
                    // 这个节点已经没用了，它的唯一作用就是找右节点，它的使命已经完成了，所以不需要再入栈了
                    // stack.push(cur);
                    cur = cur.right;
                    flag = false;
                } else {
                    if(stack.isEmpty())
                        break;
                    cur = stack.pop();
                    flag = true;
                }
            } else {
                System.out.print(cur.value + " ");
                if(cur.left != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    flag = true;
                }
            }
        }
    }

    /**
     * 使用栈中序遍历
     * @param root
     */
    static void stackMidOrderTraversal(TreeNode<?> root) {
        if(root == null)
            return;
        Stack<TreeNode<?>> stack = new Stack<>();
        TreeNode<?> cur = root;
        boolean flag = false;
        for(;;) {
            if(flag) {
                if(cur.right != null) {
                    // 这个节点已经没用了，它的唯一作用就是找右节点，它的使命已经完成了，所以不需要再入栈了
                    // stack.push(cur);
                    cur = cur.right;
                    flag = false;
                } else {
                    if(stack.isEmpty())
                        break;
                    cur = stack.pop();
                    System.out.print(cur.value + " ");
                    flag = true;
                }
            } else {
                if(cur.left != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    System.out.print(cur.value + " ");
                    flag = true;
                }
            }
        }
    }

    /**
     * 使用栈后序遍历
     * @param root
     */
    static void stackPostOrderTraversal(TreeNode<?> root) {
        if(root == null)
            return;
        Stack<TreeNode<?>> stack = new Stack<>();
        // 保存根节点，用于访问遍历完左右后的根节点
        Stack<TreeNode<?>> rootStack = new Stack<>();
        TreeNode<?> cur = root;
        boolean flag = false;
        for(;;) {
            if(flag) {
                // 遍历右
                if(cur.right != null) {
                    // 这个节点已经没用了，它的唯一作用就是找右节点，它的使命已经完成了，所以不需要再入栈了
                    // stack.push(cur);
                    rootStack.push(cur);
                    cur = cur.right;
                    flag = false;
                } else {
                    System.out.print(cur.value + " ");
                    if(!rootStack.isEmpty())
                        System.out.print(rootStack.pop().value + " ");
                    if(stack.isEmpty()) {
                        while(!rootStack.isEmpty()) // 如果根节点还没遍历完，遍历完根节点再退出
                            System.out.print(rootStack.pop().value + " ");
                        break;
                    }
                    cur = stack.pop();
                    flag = true;
                }
            } else {
                // 遍历左
                if(cur.left != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    flag = true;
                }
            }
        }
    }

    /**
     * 前序遍历
     * @param treeNode
     */
    static void preRootOrderTraversal(TreeNode<?> treeNode) {
        if(treeNode == null)
            return;
        System.out.print(treeNode.value + " ");
        preRootOrderTraversal(treeNode.left);
        preRootOrderTraversal(treeNode.right);
    }

    /**
     * 中序遍历
     * @param treeNode
     */
    static void midRootOrderTraversal(TreeNode<?> treeNode) {
        if(treeNode == null)
            return;
        midRootOrderTraversal(treeNode.left);
        System.out.print(treeNode.value + " ");
        midRootOrderTraversal(treeNode.right);
    }

    /**
     * 后续遍历
     * @param treeNode
     */
    static void postRootOrderTraversal(TreeNode<?> treeNode) {
        if(treeNode == null)
            return;
        postRootOrderTraversal(treeNode.left);
        postRootOrderTraversal(treeNode.right);
        System.out.print(treeNode.value + " ");
    }

    static <T> TreeNode<T> buildTree(LinkedList<T> list) {
        if(list == null || list.isEmpty())
            return null;
        T t = list.removeFirst();
        TreeNode<T> node = null;
        if(t != null) {
            node = new TreeNode<>();
            node.value = t;
            node.left = buildTree(list);
            node.right = buildTree(list);
        }
        return node;
    }

    private static class TreeNode<T> {
        T value;
        TreeNode left;
        TreeNode right;
    }
}
